// 提交链接 https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/565396968/
// 1011. 在D天内送达包裹的能力
// 完成日期： 2024.9.17
// 二分搜索
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int head = 0, tail = 0;
        for (auto& x : weights) tail += x;
        while (head < tail)
        {
            int mid = (head + tail) / 2;
            int pos = 0;
            for (int i = 0; i < days; i++)
            {
                int num = mid;
                while (pos < weights.size() && weights[pos] <= num)
                {
                    num -= weights[pos++];
                }
            }
            if (pos >= weights.size()) tail = mid;
            else head = mid + 1;
        }
        return head;
    }
};